package leetcode_bin_tree_test;

import bin_tree.TreeNode;
import sun.reflect.generics.tree.Tree;

import java.util.Arrays;

/**
 * 面试题 04.02. 最小高度树
 */
public class SortedArrayToBST {
    /**
     * 创建一个高度最小的二叉搜索树。
     * @param nums 升序排列
     * @return
     */
    public static TreeNode sortedArrayToBST(int[] nums) {
        // 不断进行二分搜索，将搜索到的数作为子节点这个节点左右两边就是它的左子树和右子树
        if (nums == null || nums.length == 0) {
            return null;
        }
        if (nums.length == 1) {
            return new TreeNode(nums[0]);
        }
        int len = nums.length;
        int mid = len / 2; // 选取当前树的根结点
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, mid));
        root.right = sortedArrayToBST(Arrays.copyOfRange(nums, mid + 1, len));
        return root;
    }

    public static void main(String[] args) {
        int[] nums = new int[] {-10, -3, 0, 5, 9};
        System.out.println(sortedArrayToBST(nums));
    }
}
